# Definition for a binary tree node.
from 树.二叉树.BuildTree import *


class Solution:
    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        def dfs(low, high):
            if low > high: return [None]
            if low == high: return [TreeNode(low)]
            ans = []
            for root_node in range(low, high + 1):
                left = dfs(low, root_node - 1)
                right = dfs(root_node + 1, high)
                for l in left:
                    for r in right:
                        ans.append(TreeNode(root_node, l, r))
            return ans

        return dfs(1, n)


if __name__ == '__main__':
    s = Solution()
    r = s.generateTrees(5)
    print(len(r))
